1. Field of the Invention
This invention relates to a secret key generation method for generating entity-specific secret keys, an encryption method for encrypting information so that it cannot be comprehended by anyone other than an authorized person, a cryptographic communications method for conducting communications via ciphertext, a cryptographic communications system, a recording medium (computer-readable medium), and a propagated signal (computer data signal embodied in a carrier wave).
2. Description of the Related Art
In today's world, characterized by sophisticated information utilization, important business documents and image information are transmitted and processed in the form of electronic information over an infrastructure of computer networks. By its very nature, electronic information can be easily copied, making it extremely difficult to distinguish between the copy and the original, and information security has become a very serious problem. The realization of computer networks which support “shared computer resources,” “multi-access,” and “broad-area implementation” is particularly indispensable to the establishment of a high-level information society. However, that very realization involves aspects which are inconsistent with the security of information exchanged between authorized parties. An effective technique for eliminating that inconsistency is encryption technology, which up until now, in the course of human history, has been primarily used in the fields of military operations and foreign diplomacy.
Cryptography is the process of converting information so that its meaning cannot be understood by anyone other than the authorized parties. In cryptographic operations, the conversion of the original text (plaintext) that anyone can understand to text (ciphertext) the meaning of which cannot be understood by a third party is called encryption, and the restoration of that encrypted text to plaintext is called decryption. The overall system wherein this encryption and decryption are performed is called a cryptosystem. In the processes of encryption and decryption, respectively, secret information called encryption keys and decryption keys are employed. A secret decryption key is necessary at the time of decryption, so that only a party knowledgeable of that decryption key can decrypt the cipher text. Accordingly, the confidentiality of the information is maintained by the encryption.
The encryption key and decryption key may be the same or they may be different. A cryptosystem wherein both keys are the same is called a common key cryptosystem, and the DES (Data Encryption Standards) adopted by the Bureau of Standards of the U.S. Department of Commerce is a typical example thereof. Conventional examples of such common key encryption schemes can be divided into the following three types.
(1) Type 1
All common keys possibly shared by other parties (entities) who may communicate with yourself by way of cryptographic communications are held in secret.
(2) Type 2
Keys are shared by a remote party and yourself via a preparatory communication each time before cryptographic communications are conducted (including Diffie-Hellman-based key sharing scheme, key delivery schemes based on public key schemes, etc.)
(3) Type 3
Disclosed specifying information (ID (identity) information) that specifies each of individuals concerned, such as a sender's (entity) name and address, a receiver's (entity) name and address, etc., is used, and both the sending entity and receiving entity independently generate the same common key without preparatory communications (including KPS (key predistribution system), ID-NIKS (ID-based non-interactive key sharing scheme), etc.).
Such conventional methods as seen in these three types of schemes are subject to the problems described below. With the method of type 1, all of the common keys are stored, wherefore this scheme is unsuitable for a network community wherein users in unspecified large numbers become entities and conduct cryptographic communications. With the method of type 2, the preparatory communications are required for key sharing.
The method of type 3 is a convenient method because it requires no preparatory communications, and a common key with an arbitrary party can be generated using the disclosed specifying information (ID information) of that party together with characteristic secret parameters distributed beforehand from a center. Nevertheless, this scheme is subject to the following two problems. Firstly, the center must become a “big brother” (creating a key escrow system wherein the center holds the secrets of all of the entities). Secondly, there is a possibility that some number of entities could collude to compute the center secrets. In the face of this collusion problem, many innovative techniques have been devised to circumvent the problem by way of computation volume, but a complete solution is very difficult.
The difficulties of resolving this collusion problem arise from the fact that the secret parameters based on the specifying information (ID information) form dual structures comprising center secrets and personal secrets. With the method 3, a cryptosystem is configured using the disclosed parameters of the center, the disclosed specifying information (ID information) of the individual entities, and these two types of secret parameters. Not only so, but it is necessary also to make it so that center secrets will not be revealed even if the entities compare the personal secrets distributed to each. Accordingly, there are many problems that must be resolved before this cryptosystem can be actually realized.
Thereupon, the inventors proposed in Japanese Patent Application No. H11-16257/1999 filed on Jan. 25, 1999, Japanese Patent Application No. H11-59049/1999 filed on Mar. 5, 1999 and corresponding U.S. patent application Ser. No. 09/489,696 fled on Jan. 24, 2000 claiming priority of these two Japanese Patent Applications and entitled “SECRET KEY GENERATION METHOD, ENCRYPTION METHOD, CRYPTOGRAPHIC COMMUNICATIONS METHOD, COMMON KEY GENERATOR, CRYPTOGRAPHIC COMMUNICATIONS SYSTEM, AND RECORDING MEDIA”, hereinafter collectively referred to as “preceding inventions”, secret key generation methods, together with encryption methods and cryptographic communications methods, based on ID-NIKS wherein the specifying information (ID information) of each of a plurality of entities is divided into a plurality of portions, these portions of divided ID information are sent to a plurality of centers respectively, the centers prepare secret keys based on the entity's divided ID information, and the secret keys are sent back to the entity from the centers. This secret key preparation and distribution is conducted for other entities. By doing so, the mathematical structures can be held down to a minimum, the collusion problem can be avoided, and the cryptosystem can easily built up. The entire disclosures of the above-mentioned two Japanese Patent Applications and single U.S. patent application are incorporated herein by reference.
The reason why the various cryptosystems based on entity specifying information (ID information) proposed for the purpose of resolving the collusion problem have been unsuccessful lies in excessively seeking mathematical structures to provide innovative techniques for preventing center secrets from being deduced from entity collusion information. When the mathematical structures are too complex, the method of demonstrating safety becomes very difficult. That being so, in the methods proposed in the preceding inventions, the mathematical structures are held to a bare minimum by dividing entity specifying information into a plurality of units and distributing all the secret keys created from the divided specifying information (each unit of ID information) to the entities.
In the preceding inventions, trustable centers are deployed in a plurality, and each center generates a secret key, having no mathematical structure and corresponding to one unit of divided specifying information for each of the entities, and sends that to the entity concerned. Each entity generates a common key, without performing preparatory communications, from the disclosed specifying information (ID information) of another entity to communicate with and the secret keys sent from the centers. Accordingly, no one center will be in possession of the secrets of all entities, and the centers will not become “big brothers.”
The inventors continued with research to improve this method utilizing the division of entity's ID information. This research was particularly focused on realizing an improved method that would be resistive to collusive attacks wherein a plurality of entities collude and attack a certain entity using all of their secret keys.